package srcLongestCommonSubsequence;

public class LCSNonSpaceEfficient
{

    private static int[] GetColumnUsingBackwardSpaceEfficientLCSAlgo(String firstString, String secondString)
    {
        int numFields = secondString.length() + 1;

        int[] prevIterationColumn = new int[numFields];
        int[] currentIterationColumn = new int[numFields];

        // Initialize values for base case to 0
        for (int j = numFields - 1; j >= 0; --j)
        {
            prevIterationColumn[j] = 0;
        }

        for (int i = firstString.length() - 1; i >= 0; --i)
        {
            currentIterationColumn[numFields - 1] = 0; // since this is entry corresponding to last column in matrix

            for (int j = secondString.length() - 1; j >= 0; --j)
            {
                if (secondString.charAt(j) == firstString.charAt(i))
                {
                    currentIterationColumn[j] = 1 + prevIterationColumn[j + 1];
                }
                else
                {
                    currentIterationColumn[j] = Math.max(prevIterationColumn[j], currentIterationColumn[j + 1]);
                }
            }

            // move values from currentIterationRow, to previousIterationRow to make space for next iteration
            for (int k = 0; k < numFields; ++k)
            {
                prevIterationColumn[k] = currentIterationColumn[k];
            }
        }

        return currentIterationColumn;
    }

    private static int[] GetColumnUsingForwardSpaceEfficientLCSAlgo(String firstString, String secondString)
    {
        int numFields = secondString.length() + 1;

        int[] previousIterationColumn = new int [numFields];
        int[] currentIterationColumn = new int [numFields];

        // Initialize values for base case to 0
        for (int j = 0; j < numFields; ++j)
        {
            previousIterationColumn[j] = 0;
        }

        for (int n = 1; n < firstString.length() + 1; ++n)
        {
            currentIterationColumn[0] = 0; // since this corresponds to first row entry in matrix

            for (int m = 1; m < secondString.length() + 1; ++m)
            {
                if (firstString.charAt(n - 1) == secondString.charAt(m - 1))
                {
                    currentIterationColumn[m] = 1 + previousIterationColumn[m - 1];
                }
                else
                {
                    currentIterationColumn[m] = Math.max(previousIterationColumn[m], currentIterationColumn[m - 1]);
                }
            }

            // move values from currentIterationColumn, to previousIterationColumn to make space for next iteration
            for (int k = 0; k < numFields; ++k)
            {
                previousIterationColumn[k] = currentIterationColumn[k];
            }
        }

        return currentIterationColumn;
    }

    private static int  GetLCSNonSpaceEfficient(String firstSequence,
            String secondSequence) {
        int numRows = firstSequence.length() + 1;
        int numCols = secondSequence.length() + 1;

        int[][] M = new int[numRows][numCols];
        char[][] P = new char[numRows][numCols];

        for (int i = 1; i < numRows; ++i)
        {
            for (int j = 1; j < numCols; ++j)
            {
                if (firstSequence.charAt(i - 1) == secondSequence.charAt(j - 1))
                {
                    M[i][j] = 1 + M[i-1][j-1];
                    P[i][j] = 'd';
                }
                else
                {
                    M[i][j] = Math.max(M[i-1][j], M[i][j-1]);
                    P[i][j] = M[i-1][j] > M[i][j-1] ? 'b' : 'l';
                }
            }
        }

        PrintMandP(numRows, numCols, M, P);

        PrintSolution(numRows, numCols, M, P, 5);

        return M[numRows - 1][numCols - 1];
    }

    /**
     * @param args
     */
    public static void main(String[] args)
    {
        String firstSequence = "";
        String secondSequence = "";

        int length1 = GetLCSNonSpaceEfficient(firstSequence, secondSequence);
        int length2[] = GetColumnUsingForwardSpaceEfficientLCSAlgo(firstSequence, secondSequence);
        int length3[] = GetColumnUsingBackwardSpaceEfficientLCSAlgo(firstSequence, secondSequence);

        System.out.println("lcsLength1: " + length1);
        System.out.println("lcsLength2: " + length2[secondSequence.length()]);
        System.out.println("lcsLength3: " + length3[0]);
    }

    private static void PrintMandP(int numRows, int numCols, int[][] M,
            char[][] P) {
        for (int i = numRows - 1; i >= 0; i--)
        {
            for( int j = numCols - 1; j >= 0; j--)
            {
                System.out.print(M[i][j] + "(" + P[i][j] + ")");
                System.out.print(' ');
            }

            System.out.println();
        }
    }

    private static void PrintSolution(int numRows, int numCols, int[][] M, char[][] P, int queryColumn)
    {
        /*
        if (numCols == queryColumn)
        {
            System.out.println("Middle entry: " + numRows + ", " + numCols);
            return;
        }

        if (P[numRows - 1][numCols - 1] == 'd')
        {
            PrintSolution(numRows-1, numCols-1, M, P, queryColumn);
        }
        else if (P[numRows - 1][numCols - 1] == 'b')
        {
            PrintSolution(numRows-1, numCols, M, P, queryColumn);
        }
        else
        {
            PrintSolution(numRows, numCols-1, M, P, queryColumn);
        }
        */
    }

}
